//
//  CountBinarySubstrings.swift
//  LeetCodeSummary
//
//  Created by 彭西西 on 2020/8/10.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  696. 计数二进制子串

import UIKit

/*
 696. 计数二进制子串

 给定一个字符串 s，计算具有相同数量0和1的非空(连续)子字符串的数量，并且这些子字符串中的所有0和所有1都是组合在一起的。

 重复出现的子串要计算它们出现的次数。

 示例 1 :

 输入: "00110011"
 输出: 6
 解释: 有6个子串具有相同数量的连续1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。

 请注意，一些重复出现的子串要计算它们出现的次数。

 另外，“00110011”不是有效的子串，因为所有的0（和1）没有组合在一起。
 示例 2 :

 输入: "10101"
 输出: 4
 解释: 有4个子串：“10”，“01”，“10”，“01”，它们具有相同数量的连续1和0。
 */

/*
 我们可以把字符串s按照0和1的连续分段，存在counts数组里面，例如 s = 00111011，可以得到counts = [2,3,1,2]
 这里 counts 数组中两个相邻的数一定代表的是两个不同的字符。
 假设counts中两个相邻的数字为u或者v，它们对应u个0和v个1，或者u个1和v个0。它们能组成满足条件子串数组为min(u,v)，即一对相邻的数字对答案的贡献。
 因为我们需要遍历所有相邻的数对，加起来求和就是所求结果。
 public:
     int countBinarySubstrings(string s) {
         vector<int> counts;
         int ptr = 0, n = s.size();
         while (ptr < n) {
             char c = s[ptr];
             int count = 0;
             while (ptr < n && s[ptr] == c) {
                 ++ptr;
                 ++count;
             }
             counts.push_back(count);
         }
         int ans = 0;
         for (int i = 1; i < counts.size(); ++i) {
             ans += min(counts[i], counts[i - 1]);
         }
         return ans;
     }
 };
 这个实现的时间复杂度和空间复杂度都是O(n)。
 
 对于某一个位置i，其实我们只关心 i−1 位置的 counts 值是多少，所以可以用一个 last 变量来维护当前位置的前一个位置，这样可以省去一个 counts 数组的空间。
 
 public int countBinarySubstrings(String s) {
     int ptr = 0, n = s.length(), last = 0, ans = 0;
     while (ptr < n) {
         char c = s.charAt(ptr);
         int count = 0;
         while (ptr < n && s.charAt(ptr) == c) {
             ++ptr;
             ++count;
         }
         ans += Math.min(count, last);
         last = count;
     }
     return ans;
 }
 
*/

class CountBinarySubstrings: NSObject {
    func countBinarySubstrings(_ s: String) -> Int {
        var result = 0
        var currentChar:Character = "2"
        var lastLength = 0
        var currentLength = 0
        for char in s {
            if currentChar != char {
                result += min(currentLength, lastLength)
                currentChar = char
                lastLength = currentLength
                currentLength = 1
            }else {
                currentLength += 1
            }
        }
        result += min(currentLength, lastLength)
        return result
    }
}
